<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <!-- 
        二分搜索的前提：数组是有序的

        二分搜索的思路：
        - 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束
        - 如果目标值大于或小于中间元素，则在大于或小于中间元素的那一半数组中搜索

        时间复杂度：
        - 每一次比较都使搜索范围缩小一半
        - 时间复杂度：O(logN)
     -->
</head>
<body>
    <script>
        Array.prototype.binarySearch = function(item) {
            let low = 0;
            let high = this.length - 1;
            while(low<=high) {
                const mid = Math.floor((low + high) / 2);
                const element = this[mid];
                if (element < item) { // 中间元素小于目标值，说明在右半边
                    low = mid + 1;
                } else if (element > item) { // 中间元素大于目标值，说明在左半边
                    high = mid - 1;
                } else { // 如果等于目标值
                    return mid;
                }
            }
            return -1; // 如果循环完，还是没找到，就返回-1
        }

        const res = [1, 2, 3, 4, 5].binarySearch(3);
        console.log(res);
    </script>
</body>
</html>